package HighMethod05;

import java.util.Arrays;
import java.util.Random;

/**
 * ClassName:    Main
 * Package:    HighMethod05
 * Description:
 * Datetime:    2021/4/17 0017   20:38
 * Author: 沈新源
 */
public class Main {


    public static void main(String[] args) {
        int[] arr = new int[10];
        Init_Arr(arr);

        System.out.println(Arrays.toString(arr));
    }

    private static void Init_Arr(int[] arr) {
//        for(int i=0;i<arr.length;i++){
//            arr[i] = (int) (Math.random()*10+1);      //Math.random()函数的取值范围是[0,1)
//
//        }
        Random ran = new Random();      //定义种子的话，对应的随机数其实“不随机”，没有定义种子的话，以当前的毫秒数作为种子
        /*for (int i = 0; i < arr.length; i++) {
//            arr[i] = ran.nextInt(10)+1;     //mod(10) + 1
            //思路一 方法一：如果要求不重复的初始化十个数
            int tmp = ran.nextInt(10) + 1;
            if (FindValue(arr, i, tmp) == -1) {
                arr[i] = tmp;     //mod(10) + 1
            } else {
                i--;
            }
            //思路一 方法二：如果要求不重复的初始化十个数
//            int val = ran.nextInt(10) + 1;
//            while (FindValue(arr, i, val) != -1) {
//                val = ran.nextInt(10) + 1;
//            }
//            arr[i] = val;


        }*/

        //思路一：方法三：如果要求不重复的初始化十个数
//        int x=0;
//        while(x < arr.length){
//            int val = ran.nextInt(10)+1;
//            if(FindValue(arr,x,val)==-1){
//                arr[x] = val;
//                x++;
//            }
//        }

        //思路二：查表 空间换时间
//        int []table = new int[arr.length+1];
//        int i =0;
//        while(i<arr.length){
//            int val = ran.nextInt(10)+1;
//            if(table[val] == 0){
//                arr[i] = val;
//                i++;
//                table[val] = 1;
//            }
//        }
        //思路二 方法二：哈希查表 空间换时间
        MyHashTable myHashTable = new MyHashTable(arr.length + 1);
        int i = 0;
        while (i < arr.length) {
            int val = ran.nextInt(arr.length) + 1;
            if (myHashTable.put(val)) {
                arr[i] = val;
                i++;

            }
        }
    }

    public static int FindValue(int[] ar, int n, int val) {
        int pos = -1;
        for (int i = 0; i < n; i++) {
            if (val == ar[i]) {
                pos = i;
                break;
            }
        }
        return pos;
    }

}

//哈希算法 线性哈西
class MyHashTable {
    int maxsize;

    class MyHashNode {
        int key;
        int value;
        public MyHashNode(){
            key = 0;
            value =0;
        }
    }

    MyHashNode[] table;

    public MyHashTable() {

    }

    public MyHashTable(int maxsize) {
        this.maxsize = maxsize;
        //对哈希table的初始化，要注意
        table = new MyHashNode[maxsize];
        for(int i =0;i<maxsize;i++ ) {
            table[i] = new MyHashNode();
            table[i].key = i;
            table[i].value = 0;
        }
    }

    public boolean put(int kx) {
        boolean res = false;
        for (int i = 0; i < maxsize; i++) {
            int pos = Hash_Inc(kx, i);
            if (table[pos].value == 0) {
                table[pos].key = kx;
                table[pos].value = 1;
                res = true;
                break;
            } else if (table[pos].key == kx) {
                break;
            }
        }

        return res;
    }

    private int Hash_Inc(int kx, int i) {
        return (Hash(kx) + Inc(i)) % maxsize;
    }

    //探测方式在这里体现，线性哈希 平方哈希 等等
    private int Inc(int i) {
        return i;
    }

    private int Hash(int kx) {
        return kx % maxsize;
    }
}